#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <functional>

/**
 * @brief 实现dijkstra算法
 * @version 1.0.0
 * @author galangel
 */
class Solution {
	static constexpr int inf = 0x3f3f3f3f;
	// a, b, w
	std::unordered_map<int, std::unordered_map<int, int>> grid;
public:
	/**
	 * @brief 创建图
	 * @param edges 边的两个端点和权值
	 */
	void makeGrid(std::vector<std::tuple<int, int, int>> edges) {
		for (auto& [a, b, w] : edges) {
			grid[a][b] = w;
		}
	}
	/**
	 * @brief 寻找最短加权路径
	 * @param startPos 起点
	 * @param endPos 终点
	 */
	int dijkstra(int startPos, int endPos) {
		// 当前的结点 权重
		std::unordered_map<int, int> assist;
		int curIndex = startPos;
		int curValue = 0;
		for (const auto& [a, v] : grid) {
			assist[a] = inf;
			for (const auto& [b, w] : v) {
				assist[b] = inf;
			}
		}
		while (!assist.empty() && curIndex != endPos) {
			assist.erase(curIndex);
			for (auto& [k, w] : assist) {
				if (grid[curIndex].count(k) && grid[curIndex][k] + curValue <= w) {
					w = grid[curIndex][k] + curValue;
				}
			}
			const auto&[minkey, minval] = *std::min_element(assist.begin(), assist.end(), [](auto& a, auto& b) {
				return a.second < b.second;
				});
			curIndex = minkey;
			curValue = minval;
		}
		return curValue;
	}
};

// 2024/3/26 更新
int dijkstra1(int src, int dest) {
    vector<int> arr(n, inf);
    vector<int> vis(n);
    arr[src] = 0;
    int mn = -1;
    for (int x = src; x != dest and x >= 0; x = mn) {
        vis[x] = true;
        mn = -1;
        for (int y = 0; y < n; ++y) {
            int w = g[x][y];
            arr[y] = min(arr[y], w + arr[x]);
        }
        for (int y = 0; y < n; ++y) {
            if (not vis[y] and (mn == -1 or arr[mn] > arr[y])) mn = y;
        }
    }
    return arr[dest] != inf ? arr[dest] : -1;
};

int main() {
	auto sol = std::make_unique<Solution>();
	std::vector<std::tuple<int, int, int>> edges1{
		{1,4,1},{4,3,1},{3,0,3},{0,2,1}
	};
	std::vector<std::tuple<int, int, int>> edges2{
		{1, 2, 3}, {2, 3, 5}, {1, 0, 4}, {0, 3, 1}
	};
	std::vector<std::tuple<int, int, int>> edges3{
		{ 'a', 'e', 2 }, { 'a', 'd', 8 },
		{ 'b', 'a', 7 }, { 'b', 'c', 1 },
		{ 'c', 'a', 3 }, { 'c', 'e', 4 }, { 'c', 'f', 3 },
		{ 'd', 'a', 2 }, { 'd', 'e', 1 },
		{ 'e', 'g', 2 },
		{ 'f', 'd', 10}, { 'f', 'e', 4 }, { 'f', 'g', 7 },
		{ 'g', 'd', 2 }
	};
	sol->makeGrid(edges3);
	std::cout << sol->dijkstra('b', 'd');
}